package com.jxb.four;

/**
 * trie树
 *
 * @author jiaobo
 * @date Created in 2025/1/1 19:18
 **/
public class ImplementTrie_208 {

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("ecdbha");
        trie.insert("eiijns");
        System.out.println("----");
    }

    //树节点的定义
    static class TrieNode {
        TrieNode[] children;
        boolean isEnd;
        TrieNode () {
            children = new TrieNode[26];
            isEnd = false;
        }
    }

    static class Trie {
        //Trie的根节点
        TrieNode root;

        public Trie () {
            root = new TrieNode();
        }

        public void insert(String word) {
            insertChar(word,0,root);
        }

        public boolean search(String word) {
            return searchChar(false,word,0,root);
        }

        public boolean startsWith(String prefix) {
            return searchChar(true,prefix,0,root);
        }

        //用递归实现字符串插入
        //index：用于记录插入的字符数
        private void insertChar(String word, int index, TrieNode currNode) {
            if (index == word.length()) {
                currNode.isEnd = true;
                return;
            }
            //计算字符在数组中的下标
            int charIndex = word.charAt(index) - 'a';
            if (currNode.children[charIndex] == null) {
                currNode.children[charIndex] = new TrieNode();
            }
            insertChar(word,index + 1,currNode.children[charIndex]);
        }

        //使用递归实现字符串查询
        //index:记录字符个数
        boolean searchChar(boolean isPrefix,String word,int index,TrieNode currNode) {
            if (index == word.length()) {
                return isPrefix || currNode.isEnd;
            }
            //获取当前的字符序号
            int charIndex = word.charAt(index) - 'a';
            if (currNode.children[charIndex] == null) {
                return false;
            }
            return searchChar(isPrefix,word,index+1,currNode.children[charIndex]);
        }
    }

}
